Розглянуто алгоритмічні розв'язки двох типів параметричних задач (з параметром у цільовій функції та з параметром у системі обмежень) на евклідовій комбінаторній множині сполучень з повтореннями.

З використанням елементів інтервальної геометрії побудовано математичну модель задачі розміщення кольорових прямокутників у смузі, яка має зони, з урахуванням похибок початкових даних.

Приведены результаты исследования методов и алгоритмов решения оптимизационных задач на размещениях с дополнительными ограничениями. Рассмотрены два подхода к решению данных задач: метод комбинаторного отсечения, идейно близкий методам отсечения в дискретной оптимизации, и метод построения лексикографической эквивалентности, основанный на направленном переборе классов эквивалентности.

Даний метод заснованo на розбитті простору за допомогою відношення еквівалентності. На базі лексикографічного перебору класів еквівалентності розроблено алгоритми розв'язку нового класу оптимізаційних задач - лінійної умовної евклідової задачі лексикографічної комбінаторної оптимізації.

Сформульовано постановку задачі евклідової комбінаторної оптимізації з дробово-лінійною функцією цілі на загальній множині перестановок з додатковими лінійними обмеженнями. Зроблено перехід від задачі з дробово-лінійною цільовою функцією до лінійної. Викладено підхід і розвинено метод комбінаторного відсікання розв'язку задачі комбінаторного типу з дробово-лінійними функціями цілі на перестановках.

Запропоновано точний метод комбінаторного відсікання для розв'язування задач евклідової комбінаторної оптимізаії на розміщеннях з лінійною цільовою функцією та лінійними додатковими обмеженнями. Розроблено й обгрунтовано алгоритм цього методу.

Виділено клас задач евклідової комбінаторної оптимізації, розв'язок яких можна отримати методом динамічного програмування. Алгоритм розв'язання розглянуто на прикладі задач розміщення об'єктів обслуговування.

Досліджено систему лінійних обмежень, що описує область допустимих розв'язків задач з лінійною функцією цілі, до якої зводиться задача оптимізації на розміщеннях з дробово-лінійною цільовою функцією. Установлено незвідну систему обмежень багатогранника в дробово-лінійній задачі оптимізації на розміщеннях.

Розглянуто метод розв'язування умовної задачі з дробово-лінійною функцією цілі на загальній множині розміщень. Досліджено оцінки роботи складових алгоритму розв'язування запропонованої задачі. Для перевірки практичної ефективності роботи алгоритму проведено аналіз числових експериментів.

Індекс рубрикатора НБУВ: В173.112.1

Рубрики:

Комбінаторне програмування

Шифр НБУВ: Ж26990 Пошук видання у каталогах НБУВ 

Індекс рубрикатора НБУВ: В173.112.1

Рубрики:

Комбінаторне програмування

Шифр НБУВ: Ж29144 Пошук видання у каталогах НБУВ 

Запропоновано точний метод розв'язування задачі оптимізації на розміщеннях з дробово-лінійною функцією цілі і додатковими лінійними обмеженнями. Досліджено ефективність алгоритму розв'язку задач шляхом проведення числових експериментів.

Індекс рубрикатора НБУВ: В173.112.1

Рубрики:

Комбінаторне програмування

Шифр НБУВ: Ж26990 Пошук видання у каталогах НБУВ 

Розглянуто застосування різних критеріїв прийняття рішень для знаходження оптимальної стратегії гравця в задачах комбінаторної оптимізації ігрового типу, в яких на стратегії одного гравця накладаються комбінаторні обмеження, що визначаються перестановками, а другим гравцем є природа.

Уперше поставлено загальну задачу евклідової комбінаторної оптимізації за умов невизначеності; введено поняття стохастичної мультимножини та мультимножини нечітких чисел, стохастичної евклідової комбінаторної множини, а також загальної евклідової комбінаторної множини нечітких стохастичних чисел, яка поєднує властивості обох видів невизначеності.

Розглянуто модифікацію методу комбінаторного відсікання для оптимізації на вершинно розташованих множинах, який дозволяє працювати з виродженими рішеннями допоміжних задач. Обгрунтовано вигляд нерівності - відсікання. Наведено ілюстративний приклад застосування методу.

Приведены результаты исследований методов и алгоритмов решения оптимизационных задач на множестве полиперестановок с линейными и дробно-линейными целевыми функциями. Предложены методы для задач оптимизации линейных функций с линейными ограничениями - комбинированный метод; для специальных функций - метод выпуклого продолжения на евклидовом множестве полиперестановок.

Исследованы свойства точек перестановочного многогранника и распространение известного метода решения систем линейных неравенств для нахождения общей формулы точек перестановочного многогранника при дополнительных ограничениях.

Исследована фундаментальная система решений системы неравенств, которая описывает перестановочный многогранник с дополнительными ограничениями и свойства соседних вершин перестановочного многогранника.

Исследовано распространение известного метода решения систем линейных неравенств для нахождения общей формулы точек перестановочного многогранника при дополнительных ограничениях.